package alogrithm;

import java.util.Arrays;

/**
 * @author lbw
 * @version 1.0
 * @date 2021/9/10 21:45
 */
public class MergeSortTest {

    private static int[] aux;

    public static void main(String[] args) {
        int[] a = new int[]{1, 4, 2, 5, 7, 8, 6, 9, 3};
        aux = new int[a.length];
        sort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
    }

    private static void sort(int[] a, int low, int high) {
        if (low >= high) {
            return;
        }
        int mid = (low + high) / 2;
        sort(a, low, mid);
        sort(a, mid + 1, high);
        mergeSort(a, low, mid, high);
    }

    private static void mergeSort(int[] a, int low, int mid, int high) {
        int i = low, j = mid + 1;

        for (int k = low; k <= high; k++) {
            aux[k] = a[k];
        }
        for (int k = low; k <= high; ++k) {
            if (i > mid) a[k] = aux[j++];
            else if (j > high) a[k] = aux[i++];
            else if (aux[j] < aux[i]) a[k] = aux[j++];
            else a[k] = aux[i++];
        }
    }
}
